/*
在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。

一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, ..., C_k 组成：

相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
C_1 位于 (0, 0)（即，值为 grid[0][0]）
C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。

 

示例 1：

输入：[[0,1],[1,0]]

输出：2

示例 2：

输入：[[0,0,0],[1,1,0],[1,1,0]]

输出：4

 

提示：

1 <= grid.length == grid[0].length <= 100
grid[i][j] 为 0 或 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        vector<vector<Node>> migong;
        int x_len=grid.size();
        int y_len=grid[0].size();
        if(x_len==1&&y_len==1&&grid[0][0]==0){
            return 1;
        }
        if(grid[0][0]==1||grid[x_len-1][y_len-1]==1){
            return -1;
        }
        for(int i=0;i<x_len;i++){
            vector<Node> vec_tmp;
            for(int j=0;j<y_len;j++){
                Node tmp{i,j,0,NULL,grid[i][j],false};
                vec_tmp.push_back(tmp);
            }
            migong.push_back(vec_tmp);     
        }
        vector<vector<int>> dir{{1,1},{0,1},{1,0},{-1,0},{0,-1},{-1,1},{1,-1},{-1,-1}};
        queue<Node*> bfs;
        migong[0][0].searched=true;
        migong[0][0].len=1;
        bfs.push(&migong[0][0]);
        Node* cur;
        Node* next;
        int new_x=0;
        int new_y=0;
        while(!bfs.empty()){
            cur=bfs.front();
            bfs.pop();

            for(int i=0;i<8;i++){
                new_x=cur->x+dir[i][0];
                new_y=cur->y+dir[i][1];
                if(new_x<0||new_x>=x_len||new_y<0||new_y>=y_len){
                    continue;
                }
                next=&migong[new_x][new_y];
                if((next->wall==0)&&!(next->searched)){
                    next->father=cur;
                    next->searched=true;
                    next->len=cur->len+1;
                    bfs.push(next);
                    //cout<<"("<<new_x<<","<<new_y<<")"<<endl;
                    if(next->x==x_len-1&&next->y==y_len-1){
                        //break;
                        return next->len;
                    }
                }
            }

            /
        }
        return -1;
    }

private:
    struct Node{
        int x;
        int y;
        int len;
        Node* father;
        int wall;
        bool searched;
        Node(int xx=0,int yy=0,int l=0,Node* f=NULL,int w=false,bool s=false):x(xx),y(yy),len(l),father(f),wall(w),searched(s){};
    };
};

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {

        int grid_len=grid.size();
        if(grid_len==1){
            return grid[0][0]==1?-1:1;
        }
        if(grid[0][0]==1||grid[grid_len-1][grid_len-1]==1){
            return -1;
        }
        vector<vector<bool>> visited(grid_len,vector<bool>(grid_len,false));
        vector<vector<int>> dir{{1,1},{0,1},{1,0},{-1,0},{0,-1},{-1,1},{1,-1},{-1,-1}};
        queue<pair<int,int>> pos;
        pos.push(make_pair(0,0));
        int cur_len=0;
        int x=0;
        int y=0;
        int nei_x=0;
        int nei_y=0;
        int res=0;
        while(!pos.empty()){
            cur_len=pos.size();
            res++;
            //cout<<"OK"<<endl;
            while(cur_len--){
                x=pos.front().first;
                y=pos.front().second;
                //cout<<"x:"<<x<<" y:"<<y<<endl;
                if(x==grid_len-1&&y==grid_len-1){
                    return res; 
                }
                pos.pop();
                if(visited[x][y]){
                    continue;
                }
                if(grid[x][y]==1){
                    continue;
                }
                visited[x][y]=true;
                for(auto& d:dir){
                    nei_x=x+d[0];
                    nei_y=y+d[1];
                    if(0<=nei_x&&nei_x<grid_len&&0<=nei_y&&nei_y<grid_len&&grid[nei_x][nei_y]==0){
                        pos.push(make_pair(nei_x,nei_y));
                    }
                }
            }
        }
        return -1;
    }
};